
'''
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
'''



class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        from collections import deque
        if root is None:
            return []

        p = deque()
        p.append(root)
        res = []
        while p:
            sz = len(p)
            for i in range(sz):
                q = p.popleft()
                if q.left:
                    p.append(q.left)
                if q.right:
                    p.append(q.right)
                if i == sz - 1:
                    res.append(q.val)
        
        return res
    
    def rightSideView2(self, root: Optional[TreeNode]) -> List[int]:
        global res
        res = []
        
        
        self.traver(root,0)
        return res

    def traver(self,root,depth):
        if root is None:
            return None
        if depth == len(res):
            res.append(root.val)
        depth += 1
        self.traver(root.right,depth)
        self.traver(root.left,depth)

            
        